from 常见数据结构.链表 import *
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def sort(head_):
            if not head_ or not head_.next:
                return head_
            slow = head_
            fast = head_
            prev = None
            while fast and fast.next:
                prev = slow
                fast = fast.next.next
                slow = slow.next
            fast = slow
            prev.next = None
            slow = head_
            fast = sort(fast)
            slow = sort(slow)
            ans = merge(slow, fast)
            return ans

        def merge(a, b):
            dummy = ListNode()
            p = dummy
            while a and b:
                if a.val < b.val:
                    p.next = a
                    a = a.next
                else:
                    p.next = b
                    b = b.next
                p = p.next
            if a:
                p.next = a
            else:
                p.next = b
            return dummy.next

        return sort(head)

if __name__ == '__main__':
    listnodes = build_list( [4,2,1,3])
    s = Solution()
    r = s.sortList(listnodes)
    while r:
        print(r.val,end='\t')
        r = r.next